#define _CRT_SECURE_NO_WARNINGS 1

#include"bttree.h"
#include"queue.h"

BTNode* BuySpace(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuySpace(a[*pi]);
	(*pi)++;

	root->left = BinaryTreeCreate(a,n,pi);
	root->right = BinaryTreeCreate(a,n,pi);
	return root;

}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BTNode* left = (*root)->left;
	BTNode* right = (*root)->right;
	free(*root);

	if (left)
	{
		BinaryTreeDestory(&left);
	}

	if (right)
	{
		BinaryTreeDestory(&right);
	}
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return  BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
	
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right,k-1);
}


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* ret = NULL;
	ret = BinaryTreeFind(root->left,x);
	if (ret)
	{
		return ret;
	}

	ret = NULL;
	ret = BinaryTreeFind(root->right, x);
	if (ret)
	{
		return ret;
	}

	return NULL;

}

void BinaryTreePrevOrder(BTNode* root)
{

	if (root == NULL)
	{
		return;
	}

	printf("%c ",root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);

}

void BinaryTreeInOrder(BTNode* root)
{

	if (root == NULL)
	{
		return;
	}

	BinaryTreePrevOrder(root->left);
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->right);

}


void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	printf("%c ", root->data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}

	printf("\n");

	QueueDestroy(&q);

}

int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front != NULL)
		{
			QueueDestroy(&q);
			return 0;
		}
	}
	
	QueueDestroy(&q);

	return 1;
}